

n = 853614236243688634207546433933817344184407629993511179674954104125291272948020157313135871680685854167228175073002456532923498873780676033948613876937900054708069414782793154664332423784555468540860323620027383865224409938408801760535895923725533317249930021009304220403656180773994755979915593243701765428704375524309120106778441531276713327633307316778981209960868858889973959464717593051796188278106530656542692197026221591953137337603620279668642289877570923
d = 49856277431268227491563983029661742984447538475431496459723603424918834205645380233354208799586289897412910554432582883106282422041503841857941404374449539059845479991534555368930692564678958879869692724228127112040815497849836406640783097381152450006427163653642448807287858008533082880789905403145272765499
c = 769728618052215013999888142241360378994125113251692216974641761579191427484771195099820123344499064539400660586491822997303082008527394020141360674934560402141071803154737952931779876604876480488621607161168766800135371181115666092450022941801261939544688645781841156582384896595174389620169381790993811473628388349340460546629468445975547202065165423447902579625409623707620203918033125016956838897242174623259370361398439791909603327912077620681423611935473209

import libnum
import gmpy2


pq=libnum.gcd(pow(4,d*n,n)-4,n)
print(pq)

p=n//pq
q=n//(p*p)

m=pow(c,d,p*q)
print(libnum.n2s(int(m)))